package JianZhiOffer;


/**
 * 实现函数double Power(double base, int exponent)，求base的exponent次方。
 * 不得使用库函数，同时不需要考虑大数问题。
 */
public class Solution16 {

    /**
     * 使用二分法
     * 设res = 1
     * 5^10
     * = 5^10 * res
     * = 25^5 * res
     * = 625^2 * (res * x) (这里5/2为基数，向下取整，让res = res * x)
     * = 390625^0 * res
     * 当n=0时，直接return res
     * */
    public static double myPow(double x, int n) {
        if (n < 0) return 1 / half(x, -n, 1);
        return half(x, n, 1);
    }

    public static double half(double x, int n, double res) {
        if (n == 0) return 1;
        if (n % 2 != 0) {
            return res * x * half(x * x, n / 2, res);
        }
        return res * half(x * x, n / 2, res);
    }

    public static void main(String[] args) {
        System.out.println(myPow(2, 10));
    }

}
